class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        n = len(prices)
        for i in range(n - 1, 0, -1):
            prices[i] = prices[i] - prices[i - 1]
        prices[0] = 0
        last1 = 0
        last2 = -fee
        last3 = -fee
        now1 = last1
        now3 = last3
        for i in range(1, n):
            now1 = max(last1, last2 + prices[i], last3 + prices[i])
            now2 = last1 - fee
            now3 = max(last2 + prices[i], last3 + prices[i])
            last1 = now1
            last2 = now2
            last3 = now3
        return max(now1, now3)


data = Solution()
# prices = [1, 3, 2, 8, 4, 9]
# fee = 2
# print(data.maxProfit(prices, fee))
prices = [1, 3, 7, 5, 10, 3]
fee = 3
print(data.maxProfit(prices, fee))
